package edu.dayu.demo1;

import java.util.Arrays;

/**
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 思路：利用递归的方式求 0 - n 之间每个数二进制 1 的个数。
 * 官方的思路：这些数只有奇数和偶数，偶数的这个数和 /2之后的数相等，奇数的个数 这个数 /2 之后+1个；
 *          因为一开始默认就赋值 0 了，所以0的位置计算下来还是0
 */
public class Demo4 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(fun(5)));
    }


    public static int[] fun(int a){
        int[] ints = new int[a + 1];
        for (int i = 0; i <= a; i++) {
            // 因为一开始默认就赋值 0 了，所以0的位置计算下来还是0
            ints[i] = ints[i/2]+i%2;
        }
        return ints;
    }

//    public static int [] fun (int a){
//        int[] ints = new int[a+1];
//        for (int i = 0; i <= a; i++) {
//            ints[i]=sum(i);
//        }
//        return ints;
//    }
//    public static int sum(int a){
//        int sum =0;
//        while (a>0){
//            int t = a%2;
//            a/=2;
//            if (t>0){
//                sum++;
//            }
//        }
//        return sum;
//    }
}
